package exercise;


import java.util.Random;

/**
 * @author noob
 * @version 1.0
 * @date 2021/3/17 6:31
 * 复习
 * 快排优化1:插入排序优化
 * 快排优化2：使用随机的锚点
 */
public class QuickSort3 {

    public static <E extends Comparable<E>> void sort(E[] arr){
        int left = 0;
        int right = arr.length-1;

        quciksort(arr,left,right);
    }

    private static <E extends Comparable<E>> void quciksort(E[] arr, int left, int right) {

//        if(left >= right)return;
        if(right - left <=15){
            insertionSort(arr,left,right);
            return;
        }

        int p = partition(arr,left,right);
        quciksort(arr,left,p-1);
        quciksort(arr,p+1,right);


    }

    private static <E extends Comparable<E>> void insertionSort(E[] arr, int left, int right) {

        for (int i = left; i <= right; i++) {
            E t = arr[i];
            int j;
            for ( j = i; j - 1 >= left && t.compareTo(arr[j-1]) < 0 ; j--) {
                arr[j] = arr[j-1];
            }
            arr[j] = t;
        }
        
    }

    private static <E extends Comparable<E>> int partition(E[] arr, int left, int right) {
          int index =   (new Random()).nextInt(right-left +1) +left;
          exchange(arr,left,index);




        int j = left;
        for (int i = left + 1; i <= right ; i++) {
            E t = arr[left];
            if(arr[i].compareTo(t) < 0){
                j++;
                exchange(arr,i,j);
            }
            // v > arr[i] ==> i++
        }

        exchange(arr,j,left);
        return j;
    }

    private static <E extends Comparable<E>> void exchange(E[] arr, int i, int j) {
        E temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }



    public static void main(String[] args) {
        Integer[] arr={4,6,5,2,3,8,7,1};
        QuickSort3.sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+ " ");
        }
        System.out.println();
    }
}
